package com.zyk.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * @author zhangsan
 * @date 2021/4/5 15:02
 */
public class J48 {

    // https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
    // 暴力尝试
    public static int lengthOfLongestSubstring(String s) {
        char[] str = s.toCharArray();
        int max = 0;
        for (int i = 0; i < str.length; i++) {
            max = Math.max(max, process(str, i, new HashSet<>()));
        }
        return max;
    }

    private static int process(char[] str, int i, HashSet<Character> set) {
        if(i == str.length - 1) {
            return set.contains(str[i]) ? 0: 1;
        }
        if(set.contains(str[i])) {
            return 0;
        }
        set.add(str[i]);
        return process(str, i+1, set) + 1;
    }

    // 动态规划
    public static int dp(String s) {
        char[] str = s.toCharArray();
        int max = 0;
        for (int i = 0; i < str.length; i++) {
            max = Math.max(max, process(str, i, new HashSet<>()));
        }
        return max;
    }


    // 双指针
    // 词典放着每个单词最后出现的次数
    // j往前走
    // j遇到重复值了, i看看遇到重复值的第一个位置是否在自己后面,如果是i跳到那个位置.
    // 每一步都计算一下i, j 的距离看是否更新最大值
    public static int lengthOfLongestSubstring2(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0;
        for(int j = 0; j < s.length(); j++) {
            if(dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }

    // for test
    public static void main(String[] args) {
        String str = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(str));
    }

}
